#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
using namespace std;
//class B1 {
//public:
//	B1(int i) { cout << " constructing B1" << i << endl; }
//	~B1() { cout << "destructing B1" << endl; }
//};
//class B2 {
//public:
//	B2() { cout << "constructing B2" << endl; }
//	~B2() { cout << "destructing B2" << endl; }
//};
//class C : public B2, virtual public B1 {
//	int j;
//public:
//	C(int a, int b, int c) : B1(a), memberB1(b), j(c) {}
//private:
//	B1 memberB1;
//	B2 memberB2;
//};
//int main() {
//	C obj(1, 2, 3);
//	return 0;
//}
int lastStoneWeight(vector<int>& stones) {
	priority_queue<int> heap;
	for (auto& e : stones)
		heap.push(e);
	while (heap.size() > 1)
	{
		int x = heap.top();
		heap.pop();
		int y = heap.top();
		heap.pop();
		if(x-y)
		heap.push(x - y);
	}
	return heap.top();
}
class KthLargest {
	priority_queue<int,vector<int>,greater<int>> heap;
	int _k;
public:
	KthLargest(int k, vector<int>& nums) {
		_k = k;
		for (auto& e : nums)
		{
			heap.push(e);
			if (heap.size() > k)
				heap.pop();
		}
	}

	int add(int val) {
		heap.push(val);
		if (heap.size() > _k)
			heap.pop();
		return heap.top();
	}
};
struct cmp
{
	bool operator()(const pair<string, int>& p1, const pair<string, int>& p2)
	{
		if (p1.second == p2.second)
			return p1.first < p2.first;
		return p1.second > p2.second;
	}
};
vector<string> topKFrequent(vector<string>& words, int k) {
	map<string, int> hash;
	for (auto& e : words)
		hash[e]++;
	priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> heap;
	for (auto& e : hash)
	{
		heap.push(e);
		if (heap.size() > k)
			heap.pop();
	}
	vector<string> ret(k);
	for (int i = k - 1; i--; i >= 0)
	{
		ret[i] = heap.top().first;
		heap.pop();
	}
	return ret;
}
class MedianFinder {
	priority_queue<int> left;
	priority_queue<int, vector<int>, greater<int>> right;
public:
	MedianFinder() {

	}

	void addNum(int num) {
		if (left.size() == 0 || left.size() == right.size())
		{
			if (num <= left.top())
				left.push(num);
			else
			{
				right.push(num);
				left.push(right.top());
				right.pop();
			}
		}
		else
		{
			if (num <= right.top())
			{
				left.push(num);
				right.push(left.top());
				left.pop();
			}
			else
				right.push(num);
		}
	}

	double findMedian() {
		if (left.size() == right.size())
			return (left.top() + right.top()) / 2.0;
		else
			return left.top();
	}
};
//int ret = 0,path=1;
//int m, n;
//vector<vector<int>> memory;
//void dfs(vector<vector<int>>& mat,int x,int y)
//{
//	for (int i = x; i < m; i++)
//	{
//		for (int j = y; j < n; j++)
//		{
//			for (int k = 0; k < m; k++)
//			{
//				if (mat[i][j] > mat[k][j])
//				{
//					path++;
//					ret = max(ret, path);
//					dfs(mat, k, j);
//					path--;
//				}
//			}
//			for (int k = 0; k < n; k++)
//			{
//				if (mat[i][j] > mat[i][k])
//				{
//					path++;
//					ret = max(ret, path);
//					dfs(mat, i, k);
//					path--;
//				}
//			}
//		}
//	}
//}
//int maxIncreasingCells(vector<vector<int>>& mat) {
//	 m = mat.size(), n = mat[0].size();
//	 memory.resize(m);
//	 for (int i = 0; i < m; i++)
//		 memory[i].resize(n);
//	 dfs(mat, 0, 0);
//	 return ret;
//}
int maxIncreasingCells(vector<vector<int>>& mat) {
	map<int, vector<pair<int, int>>> hash;
	int m = mat.size(), n = mat[0].size();
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			hash[mat[i][j]].push_back({ i,j });
	vector<int> maxrow(m), maxcol(n);
	for (auto& e : hash)
	{
		auto& pos = e.second;
		vector<int> mx;
		for (auto& p : pos)
			mx.push_back(max(maxrow[p.first], maxcol[p.second]) + 1);
		for (int i = 0; i < pos.size(); i++)
		{
			auto& p = pos[i];
			maxrow[p.first] = max(maxrow[p.first], mx[i]);
			maxcol[p.second] = max(maxcol[p.second], mx[i]);
       	}
	}
	int ret = 0;
	for (auto& e : maxrow)
		ret = max(ret,e);
	return ret;
}
int main()
{

	return 0;
}